package leetcode_周赛._2023._06;

import java.util.Arrays;

/**
 * 第 349 场周赛
 * <p>AC_2</p>
 *
 * @author yezh
 * @date 2023/6/12 9:21
 */
public class _11 {

    /**
     * 2733、既不是最小值也不是最大值
     * 算法：模拟
     * 数组中每个数都不一样
     * 如果数组长度小于等于 2, 则直接返回 -1
     * 反之, 对数组的前三个数进心排序, 取 nums[1]
     */
    public int findNonMinOrMax(int[] nums) {
        int n = nums.length;
        if (n <= 2) return -1;
        Arrays.sort(nums, 0, 3);
        return nums[1];
    }

    /**
     * 2734、执行子串操作后的字典序最小字符串
     * 算法：模拟
     * 要求恰好一次, 所以遇到全 'a' 的情况, 要把最后一个 'a' 变成 'z'
     */
    public String smallestString(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            if (chars[i] != 'a') {
                for (int j = i; j < len && chars[j] != 'a'; j++) chars[j] = (char) (chars[j] - 1);
                return new String(chars);
            }
        }
        chars[len - 1] = 'z';
        return new String(chars);
    }

    /**
     * 2735、收集巧克力
     * 算法：贪心
     * 对于第 i 个位置, 可以移动 0 ~ n - 1 次
     * 移动第一次, 第 i 个位置可以取到的成本 min(nums[i], nums[(i + 1) % n]
     * 移动第二次, 第 i 个位置可以取到的成本 min(nums[i], nums[(i + 1) % n, nums[(i + 2) % n]
     * 移动第三次, 第 i 个位置可以取到的成本 min(nums[i], nums[(i + 1) % n, nums[(i + 2) % n, nums[(i + 3) % n]
     * ...
     * 移动第 n - 1 次, 第 i 个位置可以取到的成本 min(nums[i], nums[(i + 1) % n, nums[(i + 2) % n, ..., nums[(i + n - 1) % n]
     * 根据移动次数算, 不要根据每种类型的巧克力算
     * 做的时候想着先枚举每个点, 这样每次都要考虑移动次数, 每个点的移动次数不统一就很麻烦.
     * 因此, 转换思路很重要, 先枚举移动次数, 再枚举每个点, 这样每个点就只有两种选择, 要么移要么不移
     */
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        long[] sum = new long[n];
        // 移动 i 次需要的成本
        for (int i = 0; i < n; i++) sum[i] = (long) i * x;
        // 枚举移动次数, 即举子数组, 相当于左移, 这里左移和右移没有区别
        // 移动 0 次, nums[0] 是子数组的开头, 移动 1 次, nums[1] 是子数组的开头 ... 移动 n - 1 次, nums[n - 1] 是子数组的开头
        for (int i = 0; i < n; i++) {
            // 子数组的左端点
            int mn = nums[i];
            for (int j = i; j < n + i; j++) {
                // 移还是不移
                mn = Math.min(mn, nums[j % n]);
                // j - i 表示移动的次数
                sum[j - i] += mn;
            }
        }
        long ans = Long.MAX_VALUE;
        for (long num : sum) ans = Math.min(ans, num);
        return ans;
    }

    public long minCost_ordinary(int[] nums, int x) {
        int n = nums.length;
        long[] cost = new long[n];
        for (int i = 0; i < n; i++) cost[i] = nums[i];
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // 移动 i 次
            long minCost = 0;
            for (int j = 0; j < n; j++) {
                // cost[j]: Math.min(nums[j % n], nums[(j + 1) % n], ..., nums[(j + i) % n])
                cost[j] = Math.min(cost[j], nums[(j + i) % n]);
                minCost += cost[j];
            }
            minCost += (long) i * x;
            ans = Math.min(ans, minCost);
        }
        return ans;
    }

    public long minCost_wrong(int[] nums, int x) {
        int n = nums.length;
        int[][] cnts = new int[n][n];
        for (int i = 0; i < n; i++)
            // 操作 i 次
            for (int j = 0; j < n; j++) cnts[i][j] = i * x + nums[(j + i) % n];
        long ans = 0;
        int move = 0;
        for (int i = 0; i < n; i++) {
            int minMove = 0, minCost = cnts[0][i];
            for (int j = 0; j < n; j++)
                if (cnts[j][i] < minCost) {
                    minCost = cnts[j][i];
                    minMove = j;
                }
            ans += minCost;
            if (move < minMove) move = minMove;
            else ans -= (long) (move - minMove) * x;
        }
        return ans;
    }

}
